package com.xinwei.leetcode.二叉树;
// https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
public class _108_将有序数组转换为二叉搜索树 {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) return null;
        int middle = (left + right) / 2;
        TreeNode node = new TreeNode();
        node.val = nums[middle];
        node.right = sortedArrayToBST(nums, middle + 1, right);
        node.left = sortedArrayToBST(nums, left, middle - 1);
        return node;
    }



    /**
     * 下面都是没看题写错的， 写了非有序数组的添加，并未能保证平衡，但是，两个方法让我对引用数据类型的传递有了新的认识
     */
//    public TreeNode sortedArrayToBST(int[] nums) {
//        TreeNode root = null;
//        for (int num : nums) {
//            if (root == null) {
//                TreeNode node = new TreeNode();
//                node.val = num;
//                root = node;
//            }else {
//                add(root, num);
//            }
//        }
//        System.out.println(root.val);
//        System.out.println(root.right.val);
//        System.out.println(root.left.val);
//        return root;
//    }
//    private void add (TreeNode root, int num) {
//        // 不是第一个节点
//        // 找到该节点的父节点+
//        TreeNode parent = new TreeNode();
//        TreeNode node = root;
//        while (node != null){
//            parent = node;
//            if (num > node.val) {
//                // 和右节点进行比较
//                node = node.right;
//            }else if (num < node.val) {
//                // 和左节点进行比较
//                node = node.left;
//            }
//        }
//        //判断该数应该加到父节点的左边还是右边
//        TreeNode newNode = new TreeNode();
//        newNode.val = num;
//        if (num > parent.val) {
//            parent.right = newNode;
//        }else {
//            parent.left = newNode;
//        }
//
//    }

//    public TreeNode sortedArrayToBST(int[] nums) {
//        TreeNode root = null;
//        for (int num : nums) {
//            add(root, num);
//        }
//        System.out.println(root.val);
//        System.out.println(root.right.val);
//        System.out.println(root.left.val);
//        return root;
//    }
//    private void add (TreeNode root, int num) {
//        if (root == null) {
//            TreeNode newNode = new TreeNode();
//            newNode.val = num;
//            root = newNode;
//        }else {
//            // 不是第一个节点
//            // 找到该节点的父节点
//            TreeNode parent = new TreeNode();
//            TreeNode node = root;
//            while (node != null){
//                parent = node;
//                if (num > node.val) {
//                    // 和右节点进行比较
//                    node = node.right;
//                }else if (num < node.val) {
//                    // 和左节点进行比较
//                    node = node.left;
//                }
//            }
//            //判断该数应该加到父节点的左边还是右边
//            TreeNode newNode = new TreeNode();
//            newNode.val = num;
//            if (num > parent.val) {
//                parent.right = newNode;
//            }else {
//                parent.left = newNode;
//            }
//        }
//    }
}
